#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;

class Solution
{
    int m{}, n{};
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    bool visit[51][51]{};
public:
    int cutOffTree(vector<vector<int>>& forest)
    {
        m = forest.size(), n = forest[0].size();
        vector<pair<int, int>> trees;
        //1.先找要砍的树的下标
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++)
                if(forest[i][j] > 1)    trees.emplace_back(i, j);
        //2.根据树的大小进行升序排序
        sort(trees.begin(), trees.end(), [&](const pair<int, int>& p1, const pair<int, int>& p2)
        {
            return forest[p1.first][p1.second] < forest[p2.first][p2.second];//按两坐标在forest中对应的值排升序
        });

        int curx = 0, cury = 0;//当前位置
        int ret = 0;
        for(auto [tx, ty] : trees)//遍历每个目标位置
        {
            int step = bfs(forest, curx, cury, tx, ty);
            if(step == -1)
                return -1;
            ret += step;
            curx = tx, cury = ty;//当前位置变成砍了树的目标位置
        }
        return ret;
    }

    int bfs(const vector<vector<int>>& forest, int curx, int cury, int tx, int ty)
    {
        //刚进来站的起点就是该砍的树，走0步，否则去除了这个位置的地方去找这个位置的值就找不到了
        if(curx == tx && cury == ty)
            return 0;
        queue<pair<int, int>> q;
        q.emplace(curx, cury);
        memset(visit, 0, sizeof visit);//上一轮访问过的位置置为false
        visit[curx][cury] = true;

        int step = 0;
        while(!q.empty())
        {
            step++;
            int sz = q.size();
            while(sz--)//同时出掉同一层，否则step会多加
            {
                auto [a, b] = q.front();
                q.pop();
                for(int k=0; k<4; k++)
                {
                    int x = a+dx[k], y = b+dy[k];
                    //先得是能走的值
                    if(x>=0 && x<m && y>=0 && y<n && forest[x][y] && !visit[x][y])
                    {
                        if(x==tx && y==ty)
                            return step;
                        q.emplace(x, y);
                        visit[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }
};